package com.zhouhong.muke_leetcode;
// 反转一个单链表。
// 示例:
// 输入: 1->2->3->4->5->NULL
// 输出: 5->4->3->2->1->NULL
public class LeetCode0206 {
        public ListNode reverseList(ListNode head) {
            // 定义前一个指针
            ListNode pre = null;
            // 定义当前遍历的节点
            ListNode cur = head;
            // 循环遍历链表
            while (cur != null){
                // 定义一个临时变量，存储当前元素的下一个元素
                ListNode temp = cur.next;
                // 当前元素指向上一个元素
                cur.next = pre;
                // 前一个指针后移一位
                pre = cur;
                // 当前指针后移一位
                cur = temp;
            }
            return pre;
        }


    // 递归实现
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        // 先将head.next 为头节点的链表反转，记录为 rev
        ListNode rev = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return rev;
    }



}
